% !TEX root = disc2012.tex
%\vspace{-0.1in}
\section{Introduction}
\label{sec:intro}
\vspace{-0.1in}
Random walks play a central role in computer science  spanning a
wide range of areas in both theory and practice. 
Random walks are used
as an integral subroutine in a wide variety of network applications
ranging from token management and load balancing
to search, routing, information propagation and gathering,
network topology construction and building random spanning
trees (e.g., see \cite{DNP09-podc} and the references therein).
They are particularly useful in providing uniform and
efficient solutions to distributed control of dynamic networks
\cite{BBSB04,ZS06}.  Random walks are local and lightweight and
require little index or state maintenance which make them especially
attractive to self-organizing dynamic networks such as peer-to-peer,
overlay, and ad hoc wireless networks. In fact, in highly dynamic networks,
where the topology can change arbitrarily from round to round (as assumed
in this paper), extensive distributed algorithmic techniques that have been developed 
for the last few decades for {\em static} networks (see e.g., \cite{peleg,lynch,tel})
are not readily applicable. On the other hand, we would like  distributed algorithms to  work correctly and terminate even in networks that keep changing continuously over time (not assuming any eventual stabilization).
  Random walks being so simple and  very local (each subsequent step in the walk depends only on the neighbors of the current node and does not depend on the topological changes taking place elsewhere in the network) can serve as a powerful tool to design distributed algorithms for such highly dynamic networks.
However, it remains a challenge to show that one can indeed use random
walks to solve non-trivial distributed computation problems efficiently in such networks, with provable guarantees. Our paper is a step in this direction. \\
\indent A key purpose of random walks in  many of the network applications 
is to perform  node sampling.  While the sampling requirements in
different applications vary, whenever a true  sample is required from
a random walk of certain steps, typically all applications perform
the walk naively
--- by simply passing a token from one node to its neighbor: thus to
perform a random walk of length $\ell$ takes time linear in $\ell$. 
In prior work \cite{DNP09-podc,DasSarmaNPT10}, the problem of performing random walks
in time that is significantly faster, i.e., sublinear in $\ell$, was studied.
In \cite{DasSarmaNPT10}, a fast distributed random walk algorithm
was presented that ran in time sublinear in $\ell$, i.e., in  $\tilde{O}(\sqrt{\ell D})$ rounds (where $D$ is the network diameter). This algorithm used only small sized messages (i.e., it assumed the  standard CONGEST model of distributed computing \cite{peleg}). 
However, a main drawback of this result is that it applied only to {\em static}
networks. A major problem left open in \cite{DasSarmaNPT10}  is whether a similar approach
can be used to speed up random walks in dynamic networks. 

%\vspace{-0.04in}
The goals of this
paper are two fold: (1) giving fast distributed algorithms for performing  random walk sampling efficiently in dynamic networks,  and (2) 
applying random walks as a key subroutine to solve non-trivial distributed computation problems in dynamic networks.
Towards the first goal, we first present a rigorous framework for studying random walks in a dynamic network (cf. Section \ref{sec:model}).  (This is necessary, since it is not immediately obvious what the output of  random walk sampling in a changing network means.)  The main purpose of  our random walk algorithm is to output a random  sample close to the ``stationary distribution" (defined precisely in Section \ref{sec:model}) of the underlying dynamic network.   Our random walk algorithms work under an oblivious adversary that fully controls the dynamic network topology, but does not know the random choices made by the algorithms (cf. Section \ref{sec:results} for a precise
problem statements and results).
   We present a fast distributed random walk
algorithm that runs in $\tilde{O}(\sqrt{\tau \Phi})$ with high probability (w.h.p.) \footnote{With high probability means with probability at least $1 - 1/n^{\Omega(1)}$, where $n$ is the number of nodes in the network.}, where $\tau$ is (an upper bound on) the dynamic mixing time
and $\Phi$ is the dynamic diameter of the network respectively (cf. Section \ref{sec:algo}).  Our algorithm uses small-sized messages only and  returns a node sample that is  ``close" to the stationary distribution of the dynamic network (assuming the stationary distribution remains fixed even as the network changes). (The precise definitions of these terms are deferred to Section \ref{sec:model}). We further extend our algorithm to efficiently perform and return $k$ independent random walk samples in  $\tilde{O}(\min\{\sqrt{k\tau \Phi}, k+\tau\})$ rounds (cf. Section \ref{sec:k-algo}). This is directly useful
in the  applications considered in this paper. 

Towards the second goal, we present a key application of our fast random walk sampling algorithm (cf. Section \ref{sec:apps}). We present a fast distributed algorithm 
for the fundamental problem of  {\em information dissemination}  
(also called as {\em gossip}) in a dynamic network.  In gossip, or more generally,
$k$-gossip, there are $k$ pieces of information (or tokens) that are
initially present in some nodes and the problem is to disseminate the
$k$ tokens to all nodes. In an $n$-node network, solving $n$-gossip  allows nodes to  distributively compute any computable function of their initial inputs using messages of size $O(\log n + d)$, where $d$ is the size of the input to the single node \cite{Kuhn-stoc}.  We present a random-walk based algorithm that runs in  $\tilde{O}(\min\{n^{1/3}k^{2/3}(\tau \Phi)^{1/3}, nk\})$ rounds with high probability (cf. Section \ref{sec:apps}).  To the best of our knowledge, this is the first $o(nk)$-time  fully-distributed {\em token forwarding} algorithm that  improves over  the previous-best $O(nk)$ round distributed algorithm \cite{Kuhn-stoc}, albeit under an oblivious adversarial model.  A lower bound of $\Omega(nk/\log n)$  under the adaptive adversarial model of \cite{Kuhn-stoc}, was recently shown in \cite{DPRS-arxiv}; hence one cannot do substantially better than the $O(nk)$ algorithm in general under an adaptive adversary.

\iffalse
Our  second application is a decentralized algorithm for computing
  global metrics of the underlying dynamic network ---
 dynamic mixing time and related spectral properties (cf. Section \ref{sec:mixest}).   Such algorithms can be useful building
 blocks in the design of {\em topologically (self-)aware} dynamic networks, i.e., networks that can  monitor and regulate themselves in a decentralized fashion. For example,  efficiently computing the mixing time or the spectral gap allows  the network to monitor connectivity and expansion properties through time.


\paragraph{Organization of the paper.} In the next section (Section \ref{sec:model}) we formally define
the the dynamic graph model, random walks in dynamic networks, and also define the associated parameters. Section
\ref{sec:results} formally states the problems and presents our results. Section \ref{sec:related} talks about related work on dynamic networks and random walks and  gives a technical overview. The distributed random walk algorithms for single random walk and precise theorem statements are in Section \ref{sec:algo} and for $k$ random walks is in Section \ref{sec:k-algo}. Applications to information dissemination and decentralized spectral computation are in Section \ref{sec:apps}. We conclude with a summary and open problems in Section \ref{sec:conc}. For lack of space we place the pseudocode of the algorithms, their analysis, and full proofs in the Appendix.   
\fi

